home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / Source / Foundation / Common / ZAllocator.cpp < prev    next >
Text File  |  1997-07-27  |  9KB  |  332 lines
  1. /*
  2.  *  File:       ZAllocator.cpp
  3.  *  Summary:    Abstract base class for dynamic memory allocators.
  4.  *  Written by: Jesse Jones
  5.  *
  6.  *  Copyright ｩ 1997 Jesse Jones. 
  7.  *    For conditions of distribution and use, see copyright notice in ZTypes.h  
  8.  *
  9.  *  Change History (most recent first):
  10.  *
  11.  *         <2>     5/29/97    JDJ        No longer depends on ZMiscUtils.
  12.  *         <1>     1/29/97    JDJ        Created
  13.  */
  14.  
  15. #include <ZAllocator.h>
  16.  
  17. #include <ZExceptions.h>
  18. #include <ZFixedAllocator.h>
  19. #include <ZMemUtils.h>
  20.  
  21. #if DEBUG
  22. #include <Limits.h>
  23. #include <List.h>
  24. #include <Timer.h>
  25. #include <TypeInfo>
  26.  
  27. #include <ZNumbers.h>
  28. #endif
  29.  
  30.  
  31. //-----------------------------------
  32. //    Types
  33. //
  34. #if DEBUG
  35. struct STestBlock {
  36.     void*        ptr;
  37.     long        deleteCount;
  38.     MilliSecond    createTime;
  39.     
  40.             STestBlock()                                        {ptr = nil;}
  41.             STestBlock(void* p, long count, MilliSecond time)    {ptr = p; deleteCount = count; createTime = time;}
  42.  
  43.     bool    operator==(const STestBlock& rhs) const                {return ptr == rhs.ptr;}
  44.     bool    operator<(const STestBlock& rhs) const                {return ptr < rhs.ptr;}
  45.             // These should not be neccesary.
  46. };
  47.  
  48. typedef list<STestBlock, allocator<STestBlock> > TestList;
  49.  
  50.  
  51. // ===================================================================================
  52. //    Internal Functions
  53. // ===================================================================================
  54.  
  55. //---------------------------------------------------------------
  56. //
  57. // GetMilliSecs
  58. //
  59. //---------------------------------------------------------------
  60. static MilliSecond GetMilliSecs()
  61. {
  62.     UnsignedWide microSeconds;
  63.     Microseconds(µSeconds);
  64.  
  65.     MilliSecond seconds = (MilliSecond) (microSeconds.hi*4294967L + microSeconds.lo/1000);        // 4294967L = 2^32 / 1000
  66.     
  67.     return seconds;
  68. }
  69.  
  70. #pragma mark -
  71.  
  72. // ===================================================================================
  73. //    class ZSizeDistribution
  74. // ===================================================================================
  75. class ZSizeDistribution {
  76.  
  77. public:    
  78.                     ZSizeDistribution(long maxDelay)    {mMaxDelay = maxDelay;}
  79.     
  80.     virtual ulong     GetBytes() const = 0;
  81.  
  82.     virtual long     GetDelay() const                     {return 1 + Random(mMaxDelay);}
  83.     
  84. protected:
  85.     long    mMaxDelay;
  86. };
  87.  
  88.  
  89. // ===================================================================================
  90. //    class ZRandomDistribution
  91. // ===================================================================================
  92. class ZRandomDistribution : public ZSizeDistribution {
  93.  
  94. public:    
  95.                     ZRandomDistribution(long min, long max, long maxDelay) : ZSizeDistribution(maxDelay)    {mMin = min; mMax = max;}
  96.     
  97.     virtual ulong     GetBytes() const                     {return (ulong) Random(mMin, mMax);}
  98.                     // Uniform distribution from min to max.
  99.     
  100. protected:
  101.     long    mMin;
  102.     long    mMax;
  103. };
  104.  
  105.  
  106. // ===================================================================================
  107. //    class ZPowerDistribution
  108. // ===================================================================================
  109. class ZPowerDistribution : public ZSizeDistribution {
  110.  
  111. public:    
  112.                     ZPowerDistribution(long maxDelay) : ZSizeDistribution(maxDelay)    {}
  113.     
  114.     virtual ulong     GetBytes() const;
  115.                     // 0.5 chance of returning min, 0.25 chance of returning 2*min,
  116.                     // 0.125 chance of returning 4*min, etc
  117. };
  118.  
  119.  
  120. //---------------------------------------------------------------
  121. //
  122. // ZPowerDistribution::GetBytes
  123. //
  124. //---------------------------------------------------------------
  125. ulong ZPowerDistribution::GetBytes() const                     
  126. {
  127.     ulong bytes = 8;
  128.     
  129.     while (FlipCoin() && bytes <= 4*1024L)         // limit max block since huge blocks will throw our timings off
  130.         bytes = 2*bytes;
  131.         
  132.     return bytes;
  133. }
  134.  
  135. #pragma mark -
  136.  
  137. // ===================================================================================
  138. //    class ZSelectedDistribution
  139. // ===================================================================================
  140. class ZSelectedDistribution : public ZSizeDistribution {
  141.  
  142. public:    
  143.                     ZSelectedDistribution(long maxDelay) : ZSizeDistribution(maxDelay)    {}
  144.     
  145.     virtual ulong     GetBytes() const;
  146.                     // Uniform distribution of some likely values.
  147. };
  148.  
  149.  
  150. //---------------------------------------------------------------
  151. //
  152. // ZSelectedDistribution::GetBytes
  153. //
  154. //---------------------------------------------------------------
  155. ulong ZSelectedDistribution::GetBytes() const                     
  156. {
  157.     static ulong sizes[18] = {8, 12, 14, 16, 18, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 500};
  158.     
  159.     long index = Random(18);
  160.  
  161.     ulong bytes = sizes[index];
  162.             
  163.     return bytes;
  164. }
  165. #endif    // DEBUG
  166.  
  167. #pragma mark -
  168.  
  169. // ===================================================================================
  170. //    class TAllocator
  171. // ===================================================================================
  172.  
  173. //---------------------------------------------------------------
  174. //
  175. // TAllocator::~TAllocator
  176. //
  177. //---------------------------------------------------------------
  178. TAllocator::~TAllocator()
  179. {
  180. }
  181.  
  182.  
  183. //---------------------------------------------------------------
  184. //
  185. // TAllocator::TAllocator
  186. //
  187. //---------------------------------------------------------------
  188. TAllocator::TAllocator()
  189. {
  190. }
  191.  
  192.  
  193. //---------------------------------------------------------------
  194. //
  195. // TAllocator::operator new                                [static]
  196. //
  197. //---------------------------------------------------------------
  198. void* TAllocator::operator new(size_t size)
  199. {
  200.     ASSERT(size >= sizeof(TAllocator));            // this will be used by subclasses
  201.     
  202.     void* ptr = NewPtr(size);
  203.     ThrowIfNil(ptr);
  204.     
  205.     return ptr;
  206. }
  207.  
  208.  
  209. //---------------------------------------------------------------
  210. //
  211. // TAllocator::operator delete                            [static]
  212. //
  213. //---------------------------------------------------------------
  214. void TAllocator::operator delete(void* ptr)
  215. {
  216.     if (ptr != nil)
  217.         DisposePtr((Ptr) ptr);
  218. }
  219.  
  220.  
  221. //---------------------------------------------------------------
  222. //
  223. // TAllocator::DoTest                                    [static]
  224. //
  225. //---------------------------------------------------------------
  226. #if DEBUG
  227. void TAllocator::DoTest(TAllocator& heap, const ZSizeDistribution& distribution)
  228. {        
  229.     TestList blocks;
  230.     
  231.     ulong count = 0;
  232.     
  233.     MilliSecond minTime = LONG_MAX;
  234.     MilliSecond avgTime = 0;
  235.     MilliSecond maxTime = LONG_MIN;
  236.     
  237.     MilliSecond time;
  238.     
  239.     TRACE("max   avg   min¥n");
  240.  
  241.     for (ulong i = 0; i < 16; i++) {
  242.         for (ulong j = 0; j < 1000; j++) {        
  243.         
  244.             // Delete the blocks that are marked for termination.    
  245.             TestList::iterator iter = blocks.begin();
  246.             while (iter != blocks.end()) {
  247.                 TestList::iterator pos = iter;
  248.                 STestBlock block = *iter++;
  249.                 if (block.deleteCount <= count) {
  250.                     time = GetMilliSecs();
  251.                     heap.Deallocate(block.ptr);
  252.                     time = block.createTime + (GetMilliSecs() - time);
  253.                                         
  254.                     if (time < minTime)
  255.                         minTime = time;
  256.                     if (time > maxTime)
  257.                         maxTime = time;
  258.                     avgTime += time;
  259.  
  260.                     blocks.erase(pos);
  261.                 }
  262.             }
  263.             
  264.             // Create a new block
  265.             ulong bytes = distribution.GetBytes();
  266.             long delay = distribution.GetDelay();
  267.             
  268.             time = GetMilliSecs();
  269.             void* ptr = heap.Allocate(bytes);
  270.             time = GetMilliSecs() - time;
  271.             ASSERT(ptr != nil);
  272.             
  273.             STestBlock block(ptr, (long) (count + delay), time);
  274.             blocks.push_back(block);
  275.                             
  276.             count++;
  277.         }
  278.         
  279.         TRACE("%-5d %-5d %-5d¥n", maxTime, (avgTime/count), minTime);
  280.     }
  281.     
  282.     // Delete remaining blocks so TSimpleAllocator dtor doesn't ASSERT.
  283.     TestList::iterator iter = blocks.begin();
  284.     while (iter != blocks.end()) {
  285.         STestBlock block = *iter++;
  286.         heap.Deallocate(block.ptr);
  287.     }
  288.  
  289.     TRACE("heap is %dK.¥n¥n", heap.GetHeapSize()/1024);
  290. }
  291. #endif
  292.  
  293.  
  294. //---------------------------------------------------------------
  295. //
  296. // TAllocator::TestAllocator                            [static]
  297. //
  298. // Tests are from Knuth, _The Art of Programming_ vol 1.
  299. // Tests were run on an 8500/120
  300. //
  301. // TSimpleAllocator times:
  302. //        uniform            3    2    2    2  (191K)
  303. //        power of two    2    3    3    2  (95K)
  304. //        selected vals    3    4    4    4  (95K)
  305. //
  306. // TBestFitAllocator times:
  307. //        uniform            2    3    2    4  (63K)
  308. //        power of two    4    3    2    2  (63K)
  309. //        selected vals    2    2    3    3  (63K)
  310. //
  311. //---------------------------------------------------------------
  312. #if DEBUG
  313. void TAllocator::TestAllocator(TAllocator& heap1, TAllocator& heap2, TAllocator& heap3)
  314. {    
  315.     TRACE("%s allocator times¥n", typeid(heap1).name());
  316.     
  317.     const long kDelay = 1000;                                // maximum number of iterations a block will hang around
  318.  
  319.     TRACE("Uniform distribution in [16, 500]¥n");
  320.     TAllocator::DoTest(heap1, ZRandomDistribution(16, 500, kDelay));
  321.  
  322.     TRACE("Weighted power of 2 distribution¥n");
  323.     TAllocator::DoTest(heap2, ZPowerDistribution(kDelay));
  324.  
  325.     TRACE("Uniform distribution of selected values¥n");
  326.     TAllocator::DoTest(heap3, ZSelectedDistribution(kDelay));
  327.  
  328.     TRACE("Completed allocator test.¥n¥n");
  329. }
  330. #endif
  331.  
  332.